package com.datastructures2.graph.最小生成树;

import com.datastructures.graph.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LazyPrimMST;
import edu.princeton.cs.algs4.StdRandom;

import java.util.Arrays;

/**
 * 加权无向图
 * @author MaoLin Wang
 * @date 2020/2/239:54
 */
public class EdgeWeightedGraph {
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;
    private int E;
    private Bag<Edge>[] adj;
    public EdgeWeightedGraph(int V) {
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Edge>();
        }
    }
    public EdgeWeightedGraph(int V, int E) {
        this(V);
        if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
        for (int i = 0; i < E; i++) {
            int v = StdRandom.uniform(V);
            int w = StdRandom.uniform(V);
            double weight = Math.round(100 * StdRandom.uniform()) / 100.0;
            Edge e = new Edge(v, w, weight);
            addEdge(e);
        }
    }
    public EdgeWeightedGraph(In in) {
        this(in.readInt());
        int E = in.readInt();
        if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
        for (int i = 0; i < E; i++) {
            int v = in.readInt();
            int w = in.readInt();
            validateVertex(v);
            validateVertex(w);
            double weight = in.readDouble();
            Edge e = new Edge(v, w, weight);
            addEdge(e);
        }
    }
    private void addEdge(Edge e) {
            int v = e.either();
            int w = e.other(v);
            validateVertex(v);
            validateVertex(w);
            adj[v].add(e);
            adj[w].add(e);
            E++;
    }
    public Iterable<Edge> adj(int v) {
        validateVertex(v);
        return adj[v];
    }
    public int degree(int v) {
        validateVertex(v);
        return adj[v].size();
    }
    public Iterable<Edge> edges() {
        Bag<Edge> list = new Bag<Edge>();
        for (int v = 0; v < V; v++) {
            int selfLoops = 0;
            for (Edge e : adj(v)) {
                if (e.other(v) > v) {
                    list.add(e);
                }
                else if (e.other(v) == v) { //是自环 如 1-1
                    if (selfLoops % 2 == 0) list.add(e);//对于自环，只需要添加一个副本即可，因为我们在addEdge时，添加了两条一样的边
                    selfLoops++;
                }
            }
        }
        return list;
    }
    private void validateVertex(int v) {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
    public int V() {
        return V;
    }

    public int E() {
        return E;
    }
    @Override
    public String toString() {
        return "顶点：" + V +
                ", 边=" + E +
                "\n" + Arrays.toString(adj);
    }


    public static void main(String[] args) {
        EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(4);
        edgeWeightedGraph.addEdge(new Edge(0,1,0.1));
        edgeWeightedGraph.addEdge(new Edge(0,2,0.2));
        edgeWeightedGraph.addEdge(new Edge(1,2,0.2));
        edgeWeightedGraph.addEdge(new Edge(2,3,0.2));
        edgeWeightedGraph.addEdge(new Edge(3,1,0.2));
        edgeWeightedGraph.addEdge(new Edge(2,2,0.2));
        edgeWeightedGraph.addEdge(new Edge(1,1,0.2));
        edgeWeightedGraph.addEdge(new Edge(3,3,0.2));
        Iterable<Edge> edges = edgeWeightedGraph.edges();
        for(Edge edge:edges){
            int v = edge.either();
            System.out.println(v+"-"+edge.other(v));
        }
    }

}
